/*************************************************************************
	> File Name: 002.HZOJ-47.0-1背包优化版.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  6/28 22:32:36 2021
 ************************************************************************/

#include <iostream>
using namespace std;

//优化了空间

int n, V, v[105], w[105], ans[10005];

int main() {
    cin >> V >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            ans[j] = max(ans[j], ans[j - v[i]] + w[i]);
        }
    }
    
    cout << ans[V] << endl;
    return 0;
}
